Error-correcting codes are typically used when transmitting data by way of transmission lines in which transmission errors may occur. FIG. 1 is a block diagram showing an example of the configuration of a data transmission system in which data are transmitted by way of a transmission line. For example, the data transmission system shown in FIG. 1 is provided with transmission line encoder 11 on the transmitting side and transmission line decoder 13 on the receiving side by way of transmission line 12. Using transmission line encoder 11 and transmission line decoder 13 to implement error correction eliminates the effect of transmission errors upon data that are sent from data generator 10 and to data consuming device 14.
Reed-Solomon codes and Turbo codes are known error-correcting codes. In addition, LDPC codes that exhibit capabilities that approach logic limits (Shannon limits) are receiving attention in recent years as error-correcting codes.
If k is the message length of messages (data) that have undergone LDPC encoding and n is the codeword length following encoding, parity check matrix H of LDPC code can be represented as a matrix of (n−k) rows and n columns. If the messages are S=(s1, s2, . . . , sk) and the codewords are C=(c1, c2, . . . , cn), codewords C are obtained by multiplying generator matrix G of k rows and n columns by message S. In other words, codewords C are obtained by finding C=SG. Since all codewords C satisfy the condition HCt=0, GHt=0. Further, Ct indicates the transposed vector of codeword C, and Ht indicates the transposed matrix of parity check matrix H.
As an example of the application of LDPC code, Non-patent Document 1 describes an example of the application of LDPC codes as a countermeasure for packet loss that occurs in a packet exchange network in which packet series is subjected to LDPC encoding.
The error-correcting characteristics of LDPC codes are determined by a parity check matrix. Non-patent Document 2 discloses a logical analysis of the error-correcting characteristics of LDPC codes. According to Non-patent Document 2, the error-correcting characteristics of LDPC codes are chiefly determined by the weighting distribution of the parity check matrix. The parity check matrix is almost entirely made up from element “0” but contains sporadic elements “1.” Weighting indicates the number of elements “1” that are contained in each row and each column in the parity check matrix.
The parity check matrix proposed by Robert G. Gallager, the originator of LDPC codes, is a matrix in which the weighting of rows and columns is uniform. LDPC codes according to the parity check matrix proposed by Robert G. Gallager are referred to as “regular” LDPC codes. FIG. 2 is an explanatory view showing an example of a parity check matrix of regular LDPC code. In the parity check matrix shown in FIG. 2, the weighting of each row, i.e., the number of elements “1,” is fixed (uniform) at WR, and the weighting of each column, i.e., the number of elements “1,” is fixed (uniform) at WC.
In contrast, Non-patent Document 2 clearly shows that LDPC codes according to a parity check matrix in which weighting is non-uniform and that has a specific distribution have better error-correcting characteristics than regular LDPC codes. LDPC codes realized by a parity check matrix in which weighting is non-uniform and that has a specific distribution are referred to as irregular LDPC codes.
As a method of generating a parity check matrix having an optimum weighting distribution, Patent Document 1 describes an LDPC code parity check matrix generation method in which a parity check matrix is generated based on encoding rate. In the LDPC code parity check matrix generation method described in Patent Document 1, a linear programming method is used to determine the weighting distribution. Then, after determining the number of elements “1” per row and column, a parity check matrix is generated by using pseudo-random numbers to put in the positions of elements “1.”
The error-correcting characteristics of the parity check matrix are not determined merely by the weighting distribution of rows and columns. Even given the optimum weighting distribution of rows and columns of a parity check matrix, it is known that, when the parity check matrix is represented using a bipartite graph (Tanner Graph), the occurrence of short loops having a length of 4 on the bipartite graph results in a drastic degradation of the error-correcting characteristics.
FIGS. 3A and 3B are explanatory views showing an example of a bipartite graph corresponding to a parity check matrix. FIG. 3A shows an example of a parity check matrix, and FIG. 3B shows a bipartite graph that represents the parity check matrix shown in FIG. 3A. In FIG. 3B, variable nodes correspond to each bit of a codeword, and check nodes correspond to each row of the parity check matrix. In addition, the edges that join the nodes represent elements “1” in the parity check matrix. As shown in FIGS. 3A and 3B, loops having a length of 4 will occur in a bipartite graph when there are two or more columns (common columns) having elements “1” shared between any two rows in the parity check matrix.
The decoding of LDPC codes is typically carried out by using a sum-product decoding method to estimate the original message based on codewords in which errors are superposed. If no loops occur in the parity check matrix, the sum-product decoding method is a Maximum a posteriori Probability (MAP) estimation. If loops exist in the parity check matrix, sum-product decoding method is degraded from MAP estimation and only approximates MAP estimation. As a result, a number of parity check matrix generation methods have been proposed for preventing the occurrence of loops in the parity check matrix.
In addition, the parity check matrix not only determines the error-correcting characteristics, but also determines the calculation costs (number of calculations) in encoding and the calculation costs for generating a generator matrix. Typically, O (n2) calculations are necessary for carrying out encoding, but O (n3) calculations are necessary for calculating a generator matrix.
To reduce the calculation cost for calculation of the generator matrix and the calculation cost in encoding, a method has been proposed in which a portion of a parity check matrix is constructed as a unit matrix or a triangular matrix to limit the number of calculations to O (n) during calculation for a generator matrix or encoding.
For example, Patent Document 2 describes a low-density parity-check encoding method in which the power of square matrices that represent cyclic shifts are used as partial matrices, and these partial matrices are assembled to make up a parity check matrix to prevent the generation of short loops. In the low-density parity-check encoding method described in Patent Document 2, the parity check matrix is triangulated at the same time that the generation of loops is prevented. Then, by making the generator matrix and parity check matrix equivalent, the number of calculations when encoding can be limited to O(n). In addition, in the low-density parity-check encoding method described in Patent Document 2, the cost of generating the parity check matrix is low because the parity check matrix can be generated by merely using regular shifts.
Non-Patent Document 1: Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, Daniel A. Spielman, Efficient Erasure Correcting Codes, “IEEE Transactions on Information Theory,” February 2001, Vol. 47, No. 2, pp. 569-584.
Non-Patent Document 2: Thomas J. Richardson, M. Amin Shokrollahi, Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes, “IEEE Transactions on Information Theory,” February 2001, Vol. 47, No. 2, pp. 619-637.
Patent Document 1: JP-A-2003-198383 (pp. 4-10, FIGS. 1-18)
Patent Document 2: JP-A-2003-115768 (pp. 6-10, FIGS. 1-9)